星尘

LeetCode - 203. 移除链表元素

发表于 更新于 分类于

203. 移除链表元素

题目

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1:

1
2
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2:

1
2
输入：head = [], val = 1
输出：[]

示例 3:

1
2
输入：head = [7,7,7,7], val = 7
输出：[]

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        # 创建虚拟节点
        dummy_node = ListNode(next=head)

        # 当前节点是虚拟节点
        current_node = dummy_node
        while current_node.next is not None:
            # 注意，这里是虚拟节点的 next.val，也就是第一个真实的节点
            if current_node.next.val == val:
                # 节点需要被删除
                current_node.next = current_node.next.next
            else:
                # 否则更新当前节点信息为下一个节点
                current_node = current_node.next
        # 返回的时候需要去掉虚拟节点
        return dummy_node.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type ListNode struct {
	Val int
	Next *ListNode
}

func removeElements(head *ListNode, val int) *ListNode {
	dummyNode := ListNode{
		Next: head,
	}
	// 注意，这里赋值的时候要使用指针，不然 currentNode 是新的一个变量。这会导致最后返回的结果不正确
	currentNode := &dummyNode
	for currentNode.Next != nil{
		if currentNode.Next.Val == val{
			currentNode.Next = currentNode.Next.Next
		}else{
			currentNode = currentNode.Next
		}
	}
	return dummyNode.Next
}

变体

总结

参考